package com.xinwei.treeExercise;

import java.util.Comparator;

/**
 * 二叉搜索树
 * @param <E>
 */
public class BinarySearchTree<E> {
    private int size = 0;
    private Node<E> root;
    private Comparator<E> comparator;



    public int size(){
        return size;
    }

    public boolean isEmpty(){
        return size == 0;
    }

    public void clear(){
        root = null;
        size = 0;
    }

    public void add(E element){
        checkElementIsNull(element);
        // 添加第一个元素
        if (root == null) {
            root.element = element;
            size++;
            return;
        }

        // 不是第一个元素
        // 找到父节点
        int compare = 0;
        Node<E> node = root;
        Node<E> parentNode = root;
        while (node != null) {
            parentNode = node;
            compare = compare(element, node.element); // 如何保证每一个对象都有比较的同时有着足够的自由度来编写自己的比较方法？
            if (compare > 0) {
                node = node.right;
            }else if (compare < 0) {
                node = node.left;
            }else {
                node.element = element;
                return;
            }
        }
        // 赋值
        Node<E> newNode = new Node<>(element, parentNode);
        if (compare > 0) {
            parentNode.right = newNode;
        }else {
            parentNode.left = newNode;
        }
        size++;
    }

    private int compare(E a1, E a2){
        if (comparator != null) {
            return comparator.compare(a1, a2);
        }
        return ((Comparable<E>)a1).compareTo(a2);
    }

    public void remove(E element){

    }

    public boolean contains(E element){
        return true;
    }

    private class Node<E>{
        E element;
        Node<E> parent;
        Node<E> left;
        Node<E> right;
        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }
    }

    private void checkElementIsNull(E element) {
        if (element == null) {
            throw new IllegalArgumentException("element can not be null");
        }
    }

}
